#include "stdio.h"

#define LEN 5

int a[LEN] = {10, 5, 2, 4, 7};

void insertion_sort(void) {
  int i, j, key;
  for (j = 1; j < LEN; j++) {
    printf("%d, %d, %d, %d, %d\n", a[0], a[1], a[2], a[3], a[4]);
    key = a[j];			/* 保存当前位置j的元素，其中[0,j-1]已经有序 */
    i = j - 1;
    while (i >= 0 && a[i] > key) {
      a[i+1] = a[i];
      i--;
    }
    a[i+1] = key;		/* 插入到合适的位置 */
  }
  printf("%d, %d, %d, %d, %d\n", a[0], a[1], a[2], a[3], a[4]);
}

int main(int argc, char *argv[])
{
  insertion_sort();
  return 0;
}

/* 插入排序是基于比较的排序
基于比较的排序，有两种基本的操作：①比较操作 ②交换操作
对于交换操作，可以优化成移动操作，即不直接进行两个元素的交换，还是用一个枢轴元素(tmp)将当前元素先保存起来，然后执行移动操作，待确定了最终位置后，再将当前元素放入合适的位置。因为，交换操作需要三次赋值，而移动操作只需要一次赋值

插入排序算法有种递归的思想在里面，它由N-1趟排序组成
第一趟 对下标 1 处的元素进行排序，保证数组[0,1]上的元素有序
第二趟 对下标 2 处的元素进行排序，保证数组[0,2]上的元素有序
...
第N-1趟对下标 N-1 处的元素进行排序，保证数组[0,N-1]上的元素有序，也就是整个数组有序了
递归思想就体现在：当对位置 i 处的元素进行排序时，[0,i-1]上的元素一定是已经有序的了

时间复杂度：O(n^2)
其他的插入排序有二分插入排序，2-路插入排序

几种常见的时间复杂度函数按数量级从小到大的顺序依次是：Θ(lgn)，Θ(sqrt(n))，Θ(n)，Θ(nlgn)，Θ(n2)，Θ(n3)，Θ(2n)，Θ(n!)

输出：
10, 5, 2, 4, 7
5, 10, 2, 4, 7
2, 5, 10, 4, 7
2, 4, 5, 10, 7
2, 4, 5, 7, 10

*/
